//给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 
//starti 到 endi （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 people ，people[i] 是第 i 个人来看花的时间。 
//
// 请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
//输出：[1,2,2,2]
//解释：上图展示了每朵花的花期时间，和每个人的到达时间。
//对每个人，我们返回他们到达时在花期内花的数目。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：flowers = [[1,10],[3,3]], people = [3,3,2]
//输出：[2,2,1]
//解释：上图展示了每朵花的花期时间，和每个人的到达时间。
//对每个人，我们返回他们到达时在花期内花的数目。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= flowers.length <= 5 * 10⁴ 
// flowers[i].length == 2 
// 1 <= starti <= endi <= 10⁹ 
// 1 <= people.length <= 5 * 10⁴ 
// 1 <= people[i] <= 10⁹ 
// 
//
// Related Topics 数组 哈希表 二分查找 有序集合 前缀和 排序 👍 138 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.TreeMap;
import java.util.stream.IntStream;

/**
 * @author ldltd
 * @date 2023-09-29 09:58:52
 * @description 2251.花期内花的数目
 */
public class NumberOfFlowersInFullBloom{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new NumberOfFlowersInFullBloom().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*思路。
		 * 把所有的花开始和结束时间加入数组排序
		 * 对于每一个人参观的时间
		 * 考虑此时最多已经开放的花start
		 * 以及此时已经结束的话end
		 * 相减即为此时他能看到的所有的花*/
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
		int n = flowers.length;
		int [] start=new int[n];
		int [] end=new int[n];
		for (int i = 0; i < n; i++) {
			start[i]=flowers[i][0];
			end[i]=flowers[i][1];
		}
		Arrays.sort(start);
		Arrays.sort(end);
		int [] res=new int[people.length];
		for (int i = 0; i < people.length; i++) {
			res[i]=findX(start,people[i]+1)-findX(end,people[i]);
		}
		return res;
	}
	//返回Nums中第一个>=x的下标。如果不存在，就返回nums.length
	private int findX(int [] nums,int x){
		int t,l=0,r=nums.length;
		while (l<r){
			t=l+(r-l)/2;
			if(nums[t]>=x){
				r=t;
			}else {
				l=t+1;
			}
		}
		return l;
	}
	//差分，把flowers [i]看做区间内每个时间点都有一朵花，
	//则得到的数组就是答案
	/*
	* 考虑一个数组a[i]
	* 前缀和s[i]表示，a[0]到a[i]的和，则i~j的区间和，可以用s[j]-s[i]得到
	* 差分和b[i]表示，b[i]=a[i]-a[i-1]  同时a[i]就是b[i]的前缀和
	* 如果要将a[i]到a[j]区间增加k，则只需在b[i]+k，同时b[j+1]-k，
	* 特别地，如果 j+1=n，则只需把 d[i] 增加 xx
	*/
	//你有一个长为 n 的数组 a，一开始所有元素均为 0。
	// 给定一些区间操作，其中 queries[i] = [left, right, x]，
// 你需要把子数组 a[left], a[left+1], ... a[right] 都加上 x。
// 返回所有操作执行完后的数组 a。
//	int[] solve(int n, int[][] queries) {
//		int[] diff = new int[n]; // 差分数组
//		for (int[] q : queries) {
//			int left = q[0], right = q[1], x = q[2];
//			diff[left] += x;
//			if (right + 1 < n) {
//				diff[right + 1] -= x;
//			}
//		}
//		for (int i = 1; i < n; i++) {
//			diff[i] += diff[i - 1]; // 直接在差分数组上复原数组 a
//		}
//		return diff;
//	}

	public int[] fullBloomFlowers1(int[][] flowers, int[] people) {
		//因为区间跨度大。用有序集合来记录
		TreeMap<Integer,Integer> cnt=new TreeMap<>();
		//构建差分数组
		for (int[] flower : flowers) {
			cnt.put(flower[0],cnt.getOrDefault(flower[0],0)+1);
			cnt.put(flower[1]+1, cnt.getOrDefault(flower[1]+1,0)-1);
		}
		int m=people.length;
		Integer[] indices= IntStream.range(0,m).boxed().toArray(Integer[]::new);
		//根据到达的天数，对people排序（且保证res的顺序）
		Arrays.sort(indices,(i,j)->people[i]-people[j]);
		int[] res=new int[m];
		int curr=0;
		for (int x : indices) {
			while (!cnt.isEmpty()&&cnt.firstKey()<=people[x]){
				curr+=cnt.pollFirstEntry().getValue();
			}
			res[x]=curr;
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
